#include <iostream>
#include <cstdlib>

/**
 * @brief AVL Tree
 * 
 * @tparam T 
 */

template<typename T> class AVL
{
private:
    struct node
    {
        T value;
        int height;
        node *left, *right;
        node(const T & theValue, node *lt, node *rt)
            : value{theValue}, height {1}, left{lt}, right{rt} {}
        node(T && theValue, node *lt, node *rt)
            : value{std::move(theValue)}, height {1}, left{lt}, right{rt} {}
        node(const T & theValue)
            : value{theValue}, height {1}, left{nullptr}, right{nullptr} {}
        node(T && theValue)
            : value{std::move(theValue)}, height {1}, left{nullptr}, right{nullptr} {}
    };
    node *root;
    bool contains(node *, const T &) const;
    node * findMin(node *) const;
    node * findMax(node *) const;
    void insert(node * &, const T &);
    void remove(node * &, const T &);
    node * clone(node *) const;
    void makeEmpty(node * &);
    void reBalance(node * &);
    void leftRotate(node * &);
    void rightRotate(node * &);
    const int getBalanceFactor(node *) const;
    const int getHeight(node *) const;

public:
    AVL(): root(nullptr) {}
    AVL(const AVL &);
    AVL(AVL &&);
    ~AVL();
    bool isEmpty() const;
    bool contains(const T &) const;
    const T & findMin() const;
    const T & findMax() const;
    void insert(const T &);
    void insert(T &&);
    void remove(const T &);
    void makeEmpty();
    AVL & operator=(const AVL & rhs);
    AVL & operator=(AVL && rhs);

};

template <typename T> AVL<T>::AVL(const AVL & rhs)
{
    root = clone(rhs.root);
}

template <typename T> AVL<T>::AVL(AVL && rhs)
{
    root = std::move(rhs.root);
}

template <typename T> AVL<T>::~AVL()
{
    makeEmpty();
}

template<typename T> bool AVL<T>::isEmpty() const
{
    return root == nullptr;
}

template<typename T> bool AVL<T>::contains(const T &x) const
{
    return contains(root, x);
}

template <typename T> AVL<T> & AVL<T>::operator=(const AVL & rhs)
{
    AVL copy(rhs);
    std::swap(*this, copy);
    return *this;
}

template <typename T> AVL<T> & AVL<T>::operator=(AVL && rhs)
{
    std::swap(root, rhs.root);
    return *this;
}

template<typename T> const T & AVL<T>::findMin() const
{
    if(isEmpty())
    {
        std::cerr << "Error! used findMin() at an empty AVL Tree!" << std::endl;
        exit(-1);
    }
    node *tmp = findMin(root);
    return tmp->value;
}

template<typename T> const T & AVL<T>::findMax() const
{
    if(isEmpty())
    {
        std::cerr << "Error! used findMax() at an empty AVL Tree!" << std::endl;
        exit(-1);
    }
    node *tmp = findMax(root);
    return tmp->value;
}

template <typename T> void AVL<T>::insert(const T & x)
{
    insert(root, x);
}

template <typename T> void AVL<T>::insert(T && x)
{
    insert(root, std::move(x));
}

template <typename T> void AVL<T>::remove(const T & x)
{
    remove(root, x);
}

template <typename T> void AVL<T>::makeEmpty()
{
    makeEmpty(root);
}

template <typename T> bool AVL<T>::contains(node *p, const T &x) const
{
    if(p == nullptr) return false;
    if(p->value == x) return true;
    return (x <= p->value) ? contains(p->left, x) : contains(p->right, x);
}

template <typename T> typename AVL<T>::node * AVL<T>::findMin(node *p) const
{
    if(p->left == nullptr) return p;
    else return findMin(p->left);
}

template <typename T> typename AVL<T>::node * AVL<T>::findMax(node *p) const
{
    if(p->right == nullptr) return p;
    else return findMax(p->right);
}

template <typename T> void AVL<T>::insert(node * &p, const T &x)
{
    //基本实现和二叉搜索树的insert是一样的，但是最后增加了更新高度和重平衡的步骤
    if(p == nullptr)
    {
        p = new node(x);
        return;
    }
    if(x <= p->value) insert(p->left, x);
    else insert(p->right, x);
    p->height = getHeight(p);
    reBalance(p);
}

template <typename T> void AVL<T>::remove(node * &p, const T &x)
{
    //基本实现和二叉搜索树的remove是一样的，但是最后增加了更新高度和重平衡的步骤
    if(p == nullptr) return;
    if(p->value == x)
    {
        if(p->left == nullptr || p->right == nullptr)
        {
            node *tmp = p;
            p = p->left ? p->left : p->right;
            delete tmp;
            return; //因为这种情况下无需对p进行高度更新以及重平衡，所以可以直接返回，而且这里如果不返回，到后面还要增加p是否为空的判断，非常麻烦
        }
        else
        {
            node *tmp = findMax(p->left);
            p->value = tmp->value;
            remove(p->left, p->value);
       }
    }
    else if(x < p->value) remove(p->left, x);
    else remove(p->right, x);
    p->height = getHeight(p);
    reBalance(p);
}

template <typename T> typename AVL<T>::node * AVL<T>::clone(node *p) const
{
    if(p == nullptr) return nullptr;
    node *newp = new node(p->value);
    newp->height = p->height;
    newp->left = clone(p->left);
    newp->right = clone(p->right);
}

template <typename T> void AVL<T>::makeEmpty(node * &p)
{
    if(p == nullptr) return;
    makeEmpty(p->left);
    makeEmpty(p->right);
    delete p;
    p = nullptr;
}

template <typename T> void AVL<T>::reBalance(node * &p)
{
    int factor = getBalanceFactor(p);
    //根据平衡因子（左右子树高度差）判断应该进行的旋转类型，分为R、LR、L、RL四种
    if(factor > 1)
    {
        if(getBalanceFactor(p->left) > 0) rightRotate(p);
        else
        {
            leftRotate(p->left);
            rightRotate(p);
       }
    }
    else if(factor < -1)
    {
        if(getBalanceFactor(p->right) < 0) leftRotate(p);
        else
        {
            rightRotate(p->right);
            leftRotate(p);
       }
   }
}

template <typename T> void AVL<T>::leftRotate(node * &p)
{
    node * tmp = p->right;
    p->right = tmp->left;
    p->height = getHeight(p); //更新高度是实现时容易遗漏的步骤
    tmp->left = p;
    tmp->height = getHeight(tmp);
    p = tmp;
}

template <typename T> void AVL<T>::rightRotate(node * &p)
{
    node * tmp = p->left;
    p->left = tmp->right;
    p->height = getHeight(p);
    tmp->right = p;
    tmp->height = getHeight(tmp);
    p = tmp;
}

template <typename T> const int AVL<T>::getBalanceFactor(node * p) const
{
    //虽然获取平衡因子很简单，但涉及到左右子树是否为空的特判，因此还是单独写一个函数来解决它
    int l = (p->left) ? (p->left->height) : 0;
    int r = (p->right) ? (p->right-> height) : 0;
    return l - r;
}

template <typename T> const int AVL<T>::getHeight(node * p) const
{
    int l = (p->left) ? (p->left->height) : 0;
    int r = (p->right) ? (p->right-> height) : 0;
    return std::max(l, r) + 1;
}


/**
 * @brief Splay Tree
 * 
 * @tparam T 
 */

template<typename T> class Splay
{
//因为实现方式的差异，私有函数的设计与AVL有较大不同，但公有函数的接口设计是一致的
private:
    struct node
    {
        T value;
        node *son[2], *father;
        node(const T & theValue, node *fa)
            : value{theValue} {son[0] = son[1] = nullptr; father = fa;}
        node(T && theValue, node *fa)
            : value{std::move(theValue)} {son[0] = son[1] = nullptr; father = fa;}
    };
    node *root;
    bool contains(node *, const T &) const;
    void findMin(node * &);
    void findMax(node * &);
    node * clone(node *) const;
    void makeEmpty(node * &);
    void rotate(node * &);
    void splay(node * &);
    node * find(const T &x);

public:
    Splay(): root(nullptr) {}
    Splay(const Splay &);
    Splay(Splay &&);
    ~Splay();
    bool isEmpty() const;
    bool contains(const T &) const;
    const T & findMin();
    const T & findMax();
    void insert(const T &);
    void insert(T &&);
    void remove(const T &);
    void makeEmpty();
    Splay & operator=(const Splay & rhs);
    Splay & operator=(Splay && rhs);

};

template <typename T> Splay<T>::Splay(const Splay & rhs)
{
    root = clone(rhs.root);
}

template <typename T> Splay<T>::Splay(Splay && rhs)
{
    root = std::move(rhs.root);
}

template <typename T> Splay<T>::~Splay()
{
    makeEmpty();
}

template<typename T> bool Splay<T>::isEmpty() const
{
    return root == nullptr;
}

template<typename T> bool Splay<T>::contains(const T &x) const
{
    return contains(root, x);
}

template <typename T> Splay<T> & Splay<T>::operator=(const Splay & rhs)
{
    Splay copy(rhs);
    std::swap(*this, copy);
    return *this;
}

template <typename T> Splay<T> & Splay<T>::operator=(Splay && rhs)
{
    std::swap(root, rhs.root);
    return *this;
}

template<typename T> const T & Splay<T>::findMin()
{
    if(isEmpty())
    {
        std::cerr << "Error! used findMin() at an empty Splay Tree!" << std::endl;
        exit(-1);
    }
    findMin(root);
    return root->value;
}

template<typename T> const T & Splay<T>::findMax()
{
    if(isEmpty())
    {
        std::cerr << "Error! used findMax() at an empty Splay Tree!" << std::endl;
        exit(-1);
    }
    findMax(root);
    return root->value;
}

template <typename T> void Splay<T>::insert(const T & x)
{
    if(root == nullptr)
    {
        root = new node(x, nullptr);
        return;
    }
    node *p = root;
    //按照寻找x的路径沿途寻找可插入点，找到后进行插入并将该点splay到根
    while(true)
    {
        int d = (x > p->value); //d表示x应该放在哪一边
        if(p->son[d] == nullptr)
        {
            p->son[d] = new node(x, p);
            root = p->son[d];
            splay(root);
            break;
        }
        else p = p->son[d];
    }
}

template <typename T> void Splay<T>::insert(T && x)
{
    insert(std::move(x));
}

template <typename T> void Splay<T>::remove(const T & x)
{
    node *p = find(x);
    //对root没有子树、仅有一个子树、有两个子树分别讨论
    if(p->son[0] == nullptr && p->son[1] == nullptr)
    {
        root = nullptr;
        delete p;
    }
    else if(p->son[0] == nullptr || p->son[1] == nullptr)
    {
        root = p->son[0] ? p->son[0] : p->son[1];
        root->father = nullptr;
        delete p;
    }
    else
    {
        //有两个子树，则先将右子树与root分离，然后将右子树的最小值splay到右子树的根，这样右子树根的左儿子就是空的，可以直接连接root的左子树
        p->son[1]->father = nullptr;
        node *q = p->son[1];
        findMin(q);
        q->son[0] = p->son[0];
        p->son[0]->father = q;
        q->father = nullptr;
        delete p;
        root = q;
    }
}

template <typename T> void Splay<T>::makeEmpty()
{
    makeEmpty(root);
}

template <typename T> bool Splay<T>::contains(node *p, const T &x) const
{
    if(p == nullptr) return false;
    if(p->value == x) return true;
    return (x <= p->value) ? contains(p->son[0], x) : contains(p->son[1], x);
}

template <typename T> void Splay<T>::findMin(node * &p)
{
    //找到最小值点后将其splay到根
    while(p->son[0]) p = p->son[0];
    splay(p);
}

template <typename T> void Splay<T>::findMax(node * &p)
{
    //找到最大值点后将其splay到根
    while(p->son[1]) p = p->son[1];
    splay(p);
}

template <typename T> typename Splay<T>::node * Splay<T>::clone(node *p) const
{
    if(p == nullptr) return nullptr;
    node *newp = new node(p->value);
    newp->height = p->height;
    newp->son[0] = clone(p->son[0]);
    newp->son[1] = clone(p->son[1]);
}

template <typename T> void Splay<T>::makeEmpty(node * &p)
{
    if(p == nullptr) return;
    makeEmpty(p->son[0]);
    makeEmpty(p->son[1]);
    delete p;
    p = nullptr;
}

template <typename T> void Splay<T>::rotate(node * &p)
{
    int d = (p == p->father->son[1]); //d表示p是它父亲的哪个儿子
    node *q = p->father;
    p->father = q->father;
    if(p->father) p->father->son[ (p->father->son[1] == q) ] = p;
    if(p->son[d^1]) p->son[d^1]->father = q;
    q->son[d] = p->son[d^1];
    p->son[d^1] = q;
    q->father = p;
}

template <typename T> void Splay<T>::splay(node * &p)
{
    while(p->father) //反复进行双旋直至p的父指针指向空，表明p已经到达根位置
    {
        node *fa = p->father;
        node *fafa = fa->father;
        if(fafa == nullptr) rotate(p);
        else rotate(fa), rotate(p);
    }
}

template <typename T> typename Splay<T>::node * Splay<T>::find(const T &x)
{
    //找到元素后将其splay到根
    node *p = root;
    while(p->value != x)
        p = (x < p->value) ? p->son[0] : p->son[1];
    root = p;
    splay(root);
    return root;
}